#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<queue>
#include<string>
using namespace std;

class Solution {
public:
    long long maximumSubsequenceCount(string text, string p) {
        long long res = 0;
        int cnt1 = 0, cnt2 = 0;
        for (char c : text)
        {
            if (c == p[1])
            {
                res += cnt1;
                ++cnt2;
            }
            if (c == p[0]) ++cnt1;
        }
        return res + max(cnt1, cnt2);
    }

    bool isValidSudoku(vector<vector<char>>& board) {
        int rows[9][9] = { 0 };
        int cols[9][9] = { 0 };
        int subboxes[3][3][9] = { 0 };
        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                char c = board[i][j];
                if (c != '.')
                {
                    int index = c - '0' - 1;
                    ++rows[i][index];
                    ++cols[j][index];
                    ++subboxes[i / 3][j / 3][index];
                    if (rows[i][index] > 1 || cols[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) return false;
                }
            }
        }
        return true;
    }

    void sortColors(vector<int>& nums) {
        int n = nums.size();
        for (int left = -1, right = n, i = 0; i < right;)
        {
            if (nums[i] == 0) swap(nums[++left], nums[i++]);
            else if (nums[i] == 1) ++i;
            else swap(nums[--right], nums[i]);
        }
    }

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[0][1] = 1;
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                if (obstacleGrid[i - 1][j - 1] == 0)dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m][n];
    }

    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size(), n = frame[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }

    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode() : val(0), left(nullptr), right(nullptr) {}
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
        TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
        
    };

    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> q;
        int levelsize = 0;
        if (root)
        {
            q.push(root);
            levelsize = 1;
        }
        vector<vector<int>> res;

        while (levelsize > 0)
        {
            vector<int> level;
            while (levelsize--)
            {
                TreeNode* front = q.front();
                q.pop();
                level.push_back(front->val);
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
            levelsize = q.size();
            res.push_back(level);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};